#include <regex.h>
#include "log.h"
#include "reg.h"
#include "pmem.h"
#include "sdb.h"
#include <string.h>
#include <assert.h>
#include <stdlib.h>
enum {
  TK_NOTYPE = 256, TK_EQ,TK_NUM,TK_AND,TK_NEGATIVE,TK_HEXNUM,TK_REGNAME,TK_POINTOR,

  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"==", TK_EQ},        // equal
  {"\\-", '-'},
  {"\\*", '*'},
  {"\\/", '/'},
  {"\\(", '('},
  {"\\)", ')'},
  {"&&",TK_AND},
  {"0[xX][0-9a-fA-F]+",TK_HEXNUM},// should before TK_NUM;
  {"[0-9]+", TK_NUM},
  {"\\$[a-z][0-9]+",TK_REGNAME}
};
#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
			assert(0);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;
static int tokens_length = 32;
static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;
static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
	if(nr_token >= tokens_length){printf("expression is too long!\n"); return 0;}// if nr_token is too big token failed
        switch (rules[i].token_type) {
  		case '+':tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case TK_EQ:tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case TK_AND:tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case '-':tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case '*':tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case '/':tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case '(':tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case ')':tokens[nr_token].type = rules[i].token_type;nr_token++;break;
  		case TK_NUM:{tokens[nr_token].type = rules[i].token_type;
			if(substr_len <= 31){
				memset(tokens[nr_token].str,'\0',32);
				strncpy(tokens[nr_token].str,substr_start,substr_len);
				nr_token ++; break;
			}
			else{printf("the num is too long, can't be longer than 31 bits");assert(substr_len <= 31);}	
				nr_token++;break;}
		//hexnum
  		case TK_HEXNUM:{tokens[nr_token].type = rules[i].token_type;
			if(substr_len <= 31){
				memset(tokens[nr_token].str,'\0',32);
				strncpy(tokens[nr_token].str,substr_start,substr_len);
				nr_token ++; break;
			}
			else{printf("the hexnum is too long, can't be longer than 31 bits");assert(substr_len <= 31);}	
				nr_token++;break;}
		case TK_REGNAME:{tokens[nr_token].type = rules[i].token_type;
			if(substr_len <= 31){
				memset(tokens[nr_token].str,'\0',32);
				strncpy(tokens[nr_token].str,substr_start,substr_len);
				nr_token ++; break;
			}
			else{printf("the reg_name is too long, can't be longer than 31 bits");assert(substr_len <= 31);}	
				nr_token++;break;}
          	default: break;
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

/* The expression is surrounded by a matched pair of parentheses.
* If that is the case, just throw away the parentheses.
*/
bool check_parentheses(int p, int q,bool*success){
	int left_cnt = 0;
	int right_cnt = 0;
	int can_rm_brackets = 1;//flag to juage if the brackets can be removed
	//if is bad expression
	for (int i = p; i<= q ;i ++)
	{
		if(tokens[i].type == '(') left_cnt++;
		if(tokens[i].type == ')') right_cnt ++;
		if(right_cnt > left_cnt) {*success = false;return false;}
	}	
	if(right_cnt != left_cnt){ *success = false; return false;}
	
	// is good expression but first is not )  or  last is not (
	if (tokens[p].type != '(' || tokens[q].type != ')') {return false;}
	// is good expression juage if can remove brackets
	left_cnt = 0;
	right_cnt = 0;
	for (int i = p+1; i< q-1 ;i ++)
	{
		if(tokens[i].type == '(') left_cnt ++;
		if(tokens[i].type == ')') right_cnt++;
		if(right_cnt > left_cnt) {can_rm_brackets = 0; break;}	
	}
	if (can_rm_brackets == 1) return true;
	return false;
}

int judge_operator_weight(int operater){
	switch (operater){
		case TK_NEGATIVE: return 2; 
		case TK_POINTOR: return 2;
		case TK_AND:return 11;
		case TK_EQ:return 7; 
		case '+':return 4;
		case '-':return 4;
		case '*':return 3;
		case '/':return 3;
		default :return 0;
	}
}
int main_operator_position(int p, int q){
	int position = p;// main operator position
	int max_weight = 0;// + - * / has different weight, + - is bigger than * /
	int new_weight = 0;
	int left_cnt = 0;// (
	int right_cnt = 0;//)
	for(int i = p; i<=q; i++)
	{
		if(tokens[i].type == '(') left_cnt ++;
		if(tokens[i].type == ')') right_cnt ++;
		if(left_cnt == right_cnt)//not in ()
		{
			if(tokens[i].type == '+'||tokens[i].type == '-'|| tokens[i].type == '*'|| tokens[i].type == '/'||tokens[i].type==TK_EQ||tokens[i].type==TK_AND||tokens[i].type == TK_NEGATIVE||tokens[i].type == TK_POINTOR)//is a operator
			{
			new_weight = judge_operator_weight(tokens[i].type);
			if(new_weight >= max_weight){ max_weight = new_weight; position = i;}
			}	
		}
	}
	return position;
}
long eval (int p, int q,bool *success,bool *div_zero){
	if(*success == false) return 0; // error had happened quick return
	if(p>q){*success = false;return 0;}
	if(p == q){
		if(tokens[p].type == TK_NUM){//num return
			char *pt;
			return strtol(tokens[p].str,&pt,10);}
		else if(tokens[p].type == TK_HEXNUM){//hex_num return
			char *pt1;
			return strtol(tokens[p].str,&pt1,16);}
		else if(tokens[p].type == TK_REGNAME){
			return (long)reg_str2val(tokens[p].str+1,success);}
		else{				//not num, bad expression
			*success = false; return 0;}
	}
	else if (check_parentheses(p,q,success) == true){
		return eval(p+1,q-1,success,div_zero);
	}
	else {
		if(*success == false) return 0;
		int op;
		long val1;
		long val2;
		op = main_operator_position(p,q);
		//if is negative not 'a-b' or * mean pointor
		if (tokens[op].type == TK_NEGATIVE|| tokens[op].type == TK_POINTOR){
			val1 = eval(p+1,q,success,div_zero);
			val2 = 1;//will never used;
		}
		else{
		val1 = eval(p,op-1,success,div_zero);
		val2 = eval(op+1,q,success,div_zero);
		}
		switch (tokens[op].type){
			case '+': return val1 + val2;
			case '-': return val1 - val2;
			case '*': return val1 * val2;
			case '/':{ 
				if (val2 == 0) {*div_zero = true;*success = false;return 0;}
				return val1 / val2;}
			case TK_EQ: return val1 == val2;
			case TK_AND:return val1 && val2;
			case TK_NEGATIVE:return -val1;
			case TK_POINTOR: return (long)paddr_read(val1,4); 
		//	default: assert(0);
			default: {*success = false;return 0;} // input expression = "87 88"
		}
		return 0;
	}
}
long expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
 
  /* TODO: Insert codes to evaluate the expression. */
 // TODO();
  bool div_zero = false;// true main div_zero;
  long eval_result = 0;

// judge if '-' mean negative
  for(int i=0;i <nr_token;i++){
	if(tokens[i].type == '-' && (i == 0||tokens[i-1].type == '('||tokens[i-1].type =='+'||tokens[i-1].type == '-'||tokens[i-1].type == '*'|| tokens[i-1].type == '/'||tokens[i-1].type == TK_EQ||tokens[i-1].type == TK_AND)){
		tokens[i].type = TK_NEGATIVE;
	}
  }
// judge if '*' mean pointer
  for(int i=0;i <nr_token;i++){
	if(tokens[i].type == '*' && (i == 0||tokens[i-1].type == '('||tokens[i-1].type =='+'||tokens[i-1].type == '-'||tokens[i-1].type == '*'|| tokens[i-1].type == '/'||tokens[i-1].type == TK_EQ||tokens[i-1].type == TK_AND)){
		tokens[i].type = TK_POINTOR;
	}
  }
  eval_result = eval(0,nr_token-1,success,&div_zero);
  if(*success) {printf("result = %ld\n",eval_result);}
  else if(div_zero == true) {printf("div_zero\n");}
  else {printf("bad expression\n");}
  return eval_result;
}
